#include <iostream>
#include <fstream>
#include <cstdlib>
#include <list>
#include <cmath>
#include <time.h>

clock_t start, end;
double cpu_time_used;

using namespace std;


//Definice structu pro stav a zasobniku pro stavy
typedef unsigned short int uint16_t;

typedef struct Stav {
	bool* konfigurace;
	uint16_t nezavisle;
	uint16_t ukazatel;
	uint16_t max;
	
	Stav(){
		konfigurace = NULL;
	}

	Stav(uint16_t pocet){
		konfigurace = new bool[pocet];
		for(uint16_t i = 0; i < pocet; i++){
			konfigurace[i] = false;
		}
		max = pocet;
		nezavisle = 0;
		ukazatel = 0;
	}

	~Stav(){
		delete [] konfigurace;
	}
	
	void nastav(Stav* stav_pointer){
		for(uint16_t i = 0; i < max; i++){
			konfigurace[i] = stav_pointer->konfigurace[i];
		}
		max = stav_pointer->max;
		nezavisle = stav_pointer->nezavisle;
		ukazatel = stav_pointer->ukazatel;
	}

	void vypis(){
		for(uint16_t i = 0; i < max; i++){
			cout << konfigurace[i];
		}
		cout << "|" << nezavisle;
	}

	bool jeMozny(bool** body){
		for(uint16_t i = 0; i < max; i++){
			if(body[ukazatel - 1][i] && konfigurace[i])
				return false;
		}
		return true;
	}

	void push(bool jak){
		if(ukazatel < max){
			konfigurace[ukazatel] = jak;
			ukazatel++;
			if(jak){
				nezavisle++;
			}	
		}
	}

	void pop(){
		ukazatel--;
		if(konfigurace[ukazatel]) nezavisle--;
		konfigurace[ukazatel] = NULL;
	}
} Stav;

class myStack{
public:
	myStack(uint16_t pocet_bodu){
		myStack::stavy = new Stav[pocet_bodu];
		myStack::aktualni_pocet = 0;
		myStack::max_pocet = pocet_bodu;
	}

	~myStack() {
		delete [] myStack::stavy;
	}

	void push(Stav* stav_local){
		if(aktualni_pocet < myStack::max_pocet){
			if(stavy[aktualni_pocet].konfigurace) delete [] stavy[myStack::aktualni_pocet].konfigurace; 
			stavy[aktualni_pocet].konfigurace = new bool[myStack::max_pocet];
			
			for(uint16_t i = 0; i < max_pocet; i++){
				stavy[aktualni_pocet].konfigurace[i] = stav_local->konfigurace[i];	
			}
			stavy[aktualni_pocet].nezavisle = stav_local->nezavisle;
			stavy[aktualni_pocet].ukazatel = stav_local->ukazatel; 
			stavy[aktualni_pocet].max = stav_local->max; 
			
			aktualni_pocet++;
		}
		else{
			cout << "Error: preteceni zasobniku" << endl;
			throw 1;
		}
	}

	void pop(){
		if(myStack::aktualni_pocet == 0){
			cout << "Error: podteceni zasobniku" << endl;
			throw 1;
		}
		else{
			myStack::aktualni_pocet--;
		}
	}

	Stav* top(){
		if(myStack::aktualni_pocet == 0){
			cout << "Error: prazdny zasobnik" << endl;
			throw 1;
		}
		else{
			return &myStack::stavy[myStack::aktualni_pocet - 1];
		}
	}

	uint16_t size(){
		return myStack::aktualni_pocet;
	}

private:
	Stav* stavy;
	uint16_t aktualni_pocet;
	uint16_t max_pocet;
};
//KONEC: Definice structu pro stav a zasobniku pro stavy

//Debug, ci podrobnejsi info?
//#define DEBUG
//#define INFO


bool** body;

int main(int argc, char* argv[]){
	uint16_t pocet_bodu; //Celkovy pocet bodu
	uint16_t pocet_hran; //Celkovy pocet hran
	uint16_t horni_mez; //Hodnota horni meze
	uint16_t dolni_mez; //Hodnota dolni meze
	uint16_t max_stupen; //Max stupen bodu
	
	fstream soubor; //Cteme ze souboru
	
	if (argc < 2) {
		cout << "Error: spatne parametry (jediny parametr je soubor)" << endl;
		return 1;
	}

	soubor.open(argv[1]);

	if (!soubor || soubor.eof()){
		cout << "Error: neni soubor, nebo je prazdny" << endl;
		return 1;
	}

	soubor >> pocet_bodu; //prvni v souboru je pocet bodu
	body = new bool*[pocet_bodu]; //podle toho alokujeme matici sousednosti
	
	Stav stav = Stav(pocet_bodu); //a take stav
	Stav max_stav = Stav(pocet_bodu); //a maximalni stav
	myStack zasobnik = myStack(pocet_bodu); //zasobnik se stavy k prozkoumani
	
	pocet_hran = 0;
	horni_mez = 0;
	max_stupen = 0;
	list<uint16_t> list_stupnu;
	uint16_t soucet_stupnu = 0;
	uint16_t stupen_uzlu;
	char bod; //pripravime nacitani po bodu
	for(uint16_t i = 0; i < pocet_bodu; i++){
		stupen_uzlu = 0;
		body[i] = new bool[pocet_bodu]; //naalokujeme radek jednoho bodu
		for(uint16_t j = 0; j < pocet_bodu; j++){
			soubor >> bod; //nacteme
			if(bod == '1'){
				body[i][j] = true;
				pocet_hran++;
				stupen_uzlu++;
			}
			else if(bod == '0'){
				body[i][j] = false;
			}
		}
		if(stupen_uzlu > max_stupen) max_stupen = stupen_uzlu;
		list_stupnu.push_back(stupen_uzlu);
	}
	pocet_hran = pocet_hran / 2;
	list_stupnu.sort();

	for(list<uint16_t>::const_iterator it = list_stupnu.begin(); it != list_stupnu.end(); ++it){
		soucet_stupnu += *it;
		++horni_mez;
		if(soucet_stupnu >= pocet_hran) break;
	}
	dolni_mez = (uint16_t)ceil((double)pocet_hran / (double)max_stupen);
#ifdef INFO
	cout << "Inicializace: OK | Pocet bodu: " << pocet_bodu << " | Pocet hran: " << pocet_hran << " | Max stupen: " << max_stupen << " | Horni mez: " << horni_mez << " | Trivialni dolni mez: " << dolni_mez << endl;
#endif

	bool konec = false;
	zasobnik.push(&stav);
	start = clock();
	while(!zasobnik.size() == 0 && !konec){
		stav.nastav(zasobnik.top()); zasobnik.pop(); //vezmeme ze zasobniku nas stav

#ifdef DEBUG 
		cout << endl << "Pracuji se stavem: "; vypis(stav); cout << " -> " << stav.ukazatel << endl;
#endif
		//stav uz nelze dal rozsirovat
		if(stav.ukazatel == stav.max)
			continue;

		//zkusime pridat false
		stav.push(false);
		
		//ma tento stav cenu? BB dolni hranice
		if(stav.max - stav.ukazatel + stav.nezavisle > max_stav.nezavisle) {
			zasobnik.push(&stav);
		}
		
		//zkusime pridat true
		stav.pop();
		stav.push(true);

		//jde tento stav pridat?
		if(stav.jeMozny(body) && (stav.max - stav.ukazatel + stav.nezavisle > max_stav.nezavisle)){
			//neni lepsi?
			if(max_stav.nezavisle < stav.nezavisle){
				max_stav.nastav(&stav);
#ifdef INFO 
				cout << "Novy nejlepsi: "; max_stav.vypis(); cout << " s " << max_stav.nezavisle << endl;
#endif
			}
			zasobnik.push(&stav);
		}

		//ma cenu dal pokracovat? //horni bound nebo prilis mnoho iteraci
		if(max_stav.nezavisle == horni_mez){
			konec = true;
		}
	}
	end = clock();
    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
	cout << "Soubor:  " << argv[1] << endl;
	cout << "Procesu: 1" << endl;
	cout << "Reseni: " << endl;
	max_stav.vypis();
	cout << endl << "Spotrebovany cas je " << cpu_time_used << endl;
	return 0;
}